package c_LinkedList;

public class LinkedList<E> {

	private class Node {//成员内部类，直接当成一个成员即可；
		private E e;
		private Node next;
		public Node(E e,Node next) {
			this.e=e;
			this.next=next;
		}
		public Node(E e) {
//			this.e=e;
//			next=null;
			this(e,null);
		}
		public Node() {
//			e=null;
//			next=null;
			this(null,null);
		}
		@Override
		public String toString() {
			return e.toString();
		}
	}	
	private int size;
	private Node dummyHead=new Node();//为了方便增删改，循环得到其前一个元素；
//  private Node dummyHead=new Node(null,null);
     
	public void addFirst(E e) {
		dummyHead.next=new Node(e,dummyHead.next);
		size++;
//		addIndex(0,e);
	}
//记住，引用指向的永远是内存空间，一个引用b赋值给另一个引用a，不代表这个引用a永远指向引用b指向的内容，而是指引用a指向*当前*引用b指向的内存空间；	
	public void addIndex(int index,E e) {
		if(index<0||index>size)
			throw new IllegalArgumentException("add failed,index is illegal.");		
		Node pre=dummyHead;	//用户是不知道有虚拟head指针的，为了方便逻辑的编写才设置的，索引依旧是以head为0开始；
		//如果链表中只有一个元素的话，其前一个元素pre是不存在的，因此为了避免特殊讨论size=1的情况，就假设出了一个虚拟节点dummyHead；
		for(int i=0;i<index;i++)//写得多了会发现 如果i从0开始，for循环 循环的次数，和i<几 保持一致；
			pre=pre.next; 		
		pre.next=new Node(e,pre.next);
		size++;
	}
	
	public void addLast(E e) {
		addIndex(size,e);
	}
	
	//这里的index只是一个形参而已，node内并不维护index变量，这本身也有悖于链表的特性；index仅仅是用来表明顺着链表走多少步长，确定删除目标而已；
	//练习用
	public E removeIndex(int index) {
		if(index<0||index>=size)
			throw new IllegalArgumentException("remove failed,index is illegal.");
		Node pre=dummyHead;
		for(int i=0;i<index;i++)
			pre=pre.next;
		Node ret=pre.next;
		pre.next=ret.next;
		ret.next=null;
		size--;
		return ret.e;				
	}//因为链表是没有索引这个概念的，为了方便用户而设计出了所谓的“索引”，这东西在底层实现里是没有的，是因为封装好了才这么说而已。。
	//add里的addFirst是指在头节点之前挂上新的节点，而removeFirst是删除头节点；这里的索引为0便是不同的含义。。这就是没有天然的固定索引导致的。。不然把这种索引当成数组索引一样那么固定；
	//此外，节点和结点的含义是不一样的。前者表示两线相交的点，而后者表示既是节点也是终点，即两线相交不再延续。
	
	public E removeFirst() {
		return removeIndex(0);
	}
	
    // 从链表中删除元素e
    public void removeElement(E e){

        Node prev = dummyHead;
        while(prev.next != null){
            if(prev.next.e.equals(e))
                break;
            prev = prev.next;
        }

        if(prev.next != null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
        }
    }
	
	public int getSize() {
		return size;
	}
	
	public void setIndex(int index,E e) {
		if(index<0||index>=size)
			throw new IllegalArgumentException("remove failed,index is illegal.");
		Node pre=dummyHead;
		for(int i=0;i<index;i++)
			pre=pre.next;
		pre.next.e=e;
	}
	
	public E getIndex(int index) {
		if(index<0||index>=size)
			throw new IllegalArgumentException("get failed,index is illegal.");
		Node pre=dummyHead;
		for(int i=0;i<index;i++)
			pre=pre.next;
		return pre.next.e;
	}
	
	public E getFirst() {
		return getIndex(0);
	}
	
	public boolean contains(E e) {
//		Node cur=dummyHead.next;
//		while(cur!=null) {
//			if(cur.e.equals(e)) {
//				return true;
//			}
//		    cur=cur.next;
//		}
//		return false;
//-------------------------------------		
//		Node cur=dummyHead.next;
//		for(int i=0;i<size;i++) {
//			if(cur.e.equals(e)) {
//				return true;
//			}
//		}
//		return false;
//-------------------------------------				
		for(Node cur=dummyHead.next;cur!=null;cur=cur.next) {
			if(cur.e.equals(e))
				return true;
		}
		return false;
		//因为cur dummyHead等都是引用，都是指针，所以本质上和int i=0；用i作指针一样；
		
	}
	
	public boolean isEmpty() {
		return size==0; 
	}
	
	@Override
	public String toString() {
		StringBuilder ret=new StringBuilder();
		ret.append("head ");
		Node cur=dummyHead.next;
		while(cur!=null) {
			ret.append(cur+"——>");
			cur=cur.next;
		}
		ret.append("null");
		return ret.toString();
	}
	
	
	
	
	
	
	

}

	